package com.company.Sort2;

import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}10:27
 */
public class MergetSort {
    static int res;
    public static void main(String[] args) {
        int[] arr = {4,5,6,7};
        int[] temp = new int[arr.length];
        getMerget(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
        System.out.println(res);
    }

    //第二步进行分化
    public static void getMerget(int[] arr,int left,int right,int[] temp){
        if (left < right){
            int mid = (left+right)/2;
            getMerget(arr,left,mid ,temp);
            getMerget(arr,mid+1,right,temp);
            merget(arr,left,right,mid,temp);
        }
    }

    //第一步(实际是在分了过后的比较阶段)
    public static void merget(int[] arr,int left,int right,int mid,int[] temp){
        int l = left;
        int r = mid + 1;
        int index = 0;//辅助数组的下标
        while (l <= mid && r <= right){//每次交換
            if (arr[l] <= arr[r]){
                temp[index] = arr[l];
                index++;
                l++;
            }else{
                temp[index] = arr[r];
                index++;
                r++;
                res += (mid - l+1);
            }
        }

        //如果左右有剩余的话
        while (l <= mid){
            temp[index] = arr[l];
            index++;
            l++;
        }

        while (r <= right){
            temp[index] = arr[r];
            index++;
            r++;
        }

        //将temp复制到arr中  灵魂
        index = 0;
        int indexLeft = left;//因为不是每次都是一个整的 有可能是零散的所以要从给的左坐标来进行给
        while (indexLeft <= right) {
            arr[indexLeft] = temp[index];
            indexLeft++;
            index++;
        }
    }
}
